CHAP, vii] PRIMITIVE ROOTS, EXPONENTS, INDICES. 183
The product of all the primitive roots of a prime p T* 3 is =1 (mod p); the sum of the primitive roots of p is ==0 if p — 1 is divisible by a square, but is s=( — l)n if p — 1 is the product of n distinct primes (arts. 80, 81).
If p is an odd prime and e is the g. c. d. of <£(?*) = pn~1(p — 1) and t, then xt = 1 (mod pn) has exactly e incongruent roots. It follows that there exist primitive roots of pn, i. e., numbers belonging to the exponent </>(pn) (arts. 85-89).
For n>2, every odd number belongs modulo 2n to an exponent which divides 2n~2, so that primitive roots of 2n are lacking; however, a modified method of employing indices to the base 5 may be used (arts. 90, 91).
If m = AaBb..., where A, J3,... are distinct primes, and cc=0(Aa), /3=4>(Bb}, - - -, and if JJL is the 1. c. m. of a, £,..., then 2M = 1 (mod m) for z prime to m. Now ju<a-/3... =<j>(m) except when ra = 2n, pn or 2pn, where p is an odd prime. Thus there exist primitive roots of m only when w = 2, 4, pn or 2pn (art. 92).
Table I, at the end of Disq. Arith., gives on one page the indices of each prime <p for each prime and power of prime modulus < 100. Gauss gave no direct table to determine the number corresponding to a given index, but indicated (end of art. 316) how his Table III for the conversion of ordinary into decimal fractions leads to the number having a given index (cf. Gauss, 15)17Ch. VI).
S. F. Lacroix8 reproduced Gauss' second proof of the existence of primitive roots of a prime, without a reference.
L. Poinsot9 argued that the primitive roots of a prime p may be obtained from the algebraic expressions for the imaginary (p — l)th roots of unity by increasing the numbers under the radical signs by such multiples of p that the radicals become integral. The <£(p —1) primitive roots of p may be obtained by excluding from 1,. . ., p — l the residues of the powers whose exponents are the distinct prime factors of p — l; while symmetrical, this method is unpractical for large p.
Fregier10 proved that the 2nth power of any odd number has the remainder unity when divided by 2n+2, if n>0.
Poinsot11 developed the first point of his preceding paper. The equation for the primitive 18th roots of unity is XQ —x3jrl =0. The roots are
But V/^3 = =t4, v^7 = 4, v-llss2 (mod 19). Thus the six primitive roots of 19 are x= —4, 2, —9, —5, —6, 3. In general, the algebraic expressions for the nth roots of unity represent the different integral roots of xn=l (mod p), where p is a prime kn-\-l} after suitable integers are added to the numbers under the radical signs. Since unity is the only (integral)
"Complement des 616mens d'algebre, Paris, ed. 3, 1804, 303-7; ed. 4, 1817, 317-321. 9M6m. Sc. Math, et Phys. de PInstitut de France, 14, 1813-5, 381-392. 10Annales de Math, (ed., Gergonne), 9, 1818-9, 285-8.. "M6m. Ac. Sc. de PInatitut de France, 4, 1819-20, 99-183.